#输入一个链表，反转链表后，输出新链表的表头。

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# class Stack:
#     def __init__(self):
#         self.list = []
#     def pop(self):
#         return self.list.pop(-1)
#     def push(self,num):
#         self.list.append(num)


def reverse_list(head):
    if head==None:
        return
    my_list = []
    while head:
        my_list.append(head)
        head=head.next
    my_list.reverse()
    for i in range(len(my_list)-1):
        my_list[i].next=my_list[i+1]
    my_list[-1].next = None
    return my_list[0]
# 这个方法可以，但是不是最好的方法，可以用中间节点，直接省略list的步骤

def ReverseList(self, pHead):
    if not pHead or not pHead.next:
        return pHead
    pre = None
    while pHead:
        tmp = pHead.next
        pHead.next = pre
        pre = pHead
        pHead = tmp
    return pre





